Minimum Number of Refueling Stops

Statement#

You need to find the minimum number of refueling stops that a car needs to make to cover a distance, target. For simplicity, assume that the car has to travel from west to east in a straight line. There are various fuel stations on the way, that are represented as a 2-D array of stations, i.e., stations[i] $= [d_i, f_i]$, where $d_i$ is the distance in miles of the $i^{th}$ gas station from the starting position, and $f_i$ is the amount of fuel in liters that it stores. Initially, the car starts with k liters of fuel. The car consumes one liter of fuel for every mile traveled. Upon reaching a gas station, the car can stop and refuel using all the petrol stored at the station. In case it cannot reach the target, the program simply returns $-1$.

Note: If the car reaches a station with $0$ fuel left, it can refuel from that station, and all the fuel from that station can be transferred to the car. If the car reaches the target with $0$ fuel left, it is still considered to have arrived.

For example:

• target: $15$
• start fuel: $2$
• stations: $[[1, 2], [2, 8], [4, 10], [6, 7], [7, 2], [8, 1]]$

If we want to reach the target of 15 miles, we have to refuel from a minimum of $2$ stations to reach the target. First, we will refuel our car with $8$ liters from the second station and then refuel $10$ liters from the third station.

Constraints:

• $1 \leq$ target, k $\leq 10^9$
• $0 \leq$ stations.length $\leq 900$
• $1 \leq d_{i} < d_{i+1}<$ target
• $1 \leq f_{i} < 10^9$

Examples#

Try it yourself#

Implement your solution in the following coding playground:

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.

Naive approach#

A naive approach is to find all the combinations of the first refueling stop, then the second refueling stop, and so on, until all the combinations of $n$ refueling stops are found. Once we have all these combinations, we will select the combination that will help us reach the target with the minimum number of refueling stops in between. To do this, we need a recursive solution to make all the possible combinations. In other words, we divide the problem into subproblems and, for each fueling station, we decide whether to include it or not in the count of refueling stations.

Now, we will see the intuition behind recursive calls. Suppose min_refuel_stops_helper(index, used) is the farthest point the car can reach by refueling at exactly the used number of refueling stations among the first index number of refueling stations. Then the recursive call will be like this:

min_refuel_stops_helper(index, used) = max(min_refuel_stops_helper(index-1, used-1) + fuel at station index , min_refuel_stops_helper(index-1, used))

For example:

• target: $100$
• start fuel: $10$
• stations: $[[10, 60], [20, 25], [30, 30]]$

With a start fuel of $10$ liters, we will check the fuel stations we can reach. As a result, we can only travel to fuel station 1 with $10$ liters of fuel. In simpler words, we can only cover a distance of $10$ miles.

After collecting all the available fuel from fuel station 1, we can cover a total distance of $70$ miles as per the following calculation:

$10$ (starting fuel) + $60$ (fuel from station 1) = $70$.

Next, we can travel to both stations 2 and 3 because the fuel required for station 2 is $20$ liters and station 3 is $30$ liters. If we choose station 2, we will end up with a total distance of $95$ miles, but this will still be less than our target distance of $100$ miles, so we will need to travel to station 3 as well and collect the available fuel, making a total distance of $125$ miles which is greater than our target. This way, to reach the target, we need to travel to 3 fueling stations.

But if we directly travel to fuel station 3 after fuel station 1, then we will end up with a total travel distance of $100$ miles, which is equal to our target of $100$ miles. This way, we only need to travel to 2 fueling stations.

So we will choose the second combination because it has the minimum number of fueling stations required to reach the target.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of this naive approach is $n\times2^n$, where $n$ is the number of available stations.

Space complexity#

The space complexity of this naive approach is $O(n)$.

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array. In the naive approach above, we do not store the maximum distance value for each combination of refueling stops for later use. Therefore, we end up computing them repeatedly.

In the memoization-based approach, we store the computed values in a lookup table when we encounter a combination of refueling stops for the first time. Prior to making a recursive call to the function, we check if the desired refueling combination result exists in the lookup table. If it does, we simply return the previously stored value. Otherwise, a recursive call is made to the function to compute the result.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of the algorithm above is $O(n^2)$, where $n$ is the number of available stations.

Space complexity#

We are using a 2-D array to store the maximum distance. So, the space complexity is $O(n^2)$.

Bottom-up solution#

The bottom-up solution, also known as the tabulation method, is an iterative method of solving dynamic programming problems. We start off by constructing a 2-D array of size $(n+1) \times (n+1)$ for tabulation, where $n$ is the total number of stations. We call this 2-D array dp and initialize it with zeroes. Now, we start filling the array in a bottom-up manner. Each entry in this array tells us the distance covered so far to reach the specific station.

Here is how we implement this algorithm:

• Initialize lookup table of size $(n+1) \times (n+1)$.

• If we do not use any fuel stop, then the max distance will be the start fuel. Therefore, we fill up the first column of the table with the start fuel.

• For each station $i$:

  • For each fueling stop $j = 1$ to $j = i$
    • If the car can reach the next station, then update the lookup table as follows: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + station i's fuel).
    • Otherwise, the max distance will be the max reachable distance of the previous station; update the lookup table as follows: dp[i][j] = dp[i - 1][j].

• After visiting all the stations, find the minimum j, which has distance >= target. This will be our minimum number of refueling stops to reach the target.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of the algorithm above is $O(n^2)$, where $n$ is the number of available stations.

Space complexity#

We are using a 2-D array of elements to store the maximum distance. So, the space complexity is $O(n^2)$.

Can we do better?#

When filling up the distance values for each station, we only require the station above it in the matrix and not any previous station’s result. This means we only need to retain the data of the last row. So, we can use a 1-D array instead of a 2-D array, which will further reduce the space complexity from $O(n^2)$ to $O(n)$.